package BlogHashBuck;

import java.util.*;

public class BlogTestOJ {

    //(搞复杂了很多)https://leetcode.cn/problems/jewels-and-stones/
    public int numJewelsInStones(String jewels, String stones) {
        HashSet<Character> set=new HashSet<>();
        HashMap<Character,Integer> map=new HashMap<>();
        //1. 遍历jewels,将宝石add进set中
        for(int i=0;i<jewels.length();i++) {
            char ch=jewels.charAt(i);
            set.add(ch);
        }
        //2. 遍历stones,建立宝石种类和数量的映射关系
        for(int i=0;i<stones.length();i++) {
            char ch=stones.charAt(i);
            if(set.contains(ch)) {  //说明这个是宝石
                if(!map.containsKey(ch)) {  //说明该宝石第一次出现
                    map.put(ch,1);//第一次出现,数量为1
                }else { //map中已有该宝石了
                    int num=map.get(ch);
                    map.put(ch,num+1);//更新该种宝石的数量
                }
            }
        }
        //3. 再次遍历set,累加宝石数量
        int ret=0;
        for(int i=0;i<jewels.length();i++) {
            char ch=jewels.charAt(i);
            if(map.containsKey(ch)) {
                ret+=map.get(ch);
            }
        }
        return ret;
    }

    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String,Integer> map=new HashMap<>();
        for(String word:words) {
            if(map.get(word)==null) {//该单词第一次出现
                map.put(word,1);
            }else {
                int num=map.get(word);
                map.put(word,num+1);
            }
        }
        PriorityQueue<Map.Entry<String,Integer>> minHeap=new PriorityQueue<>(new Comparator<>(){
            @Override
            public int compare(Map.Entry<String,Integer> o1, Map.Entry<String,Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue())==0) { //当单词数量相同时,根据键的字典序建立大根堆
                    return  o2.getKey().compareTo(o1.getKey());
                }
                return  o1.getValue().compareTo(o2.getValue());//当单词数量不同时,根据单词数量建立小根堆
            }
        });
        for(Map.Entry<String,Integer> entry:map.entrySet()) {
            if(minHeap.size()<k) {
                minHeap.offer(entry);   //取map的前k个元素建堆
            }else {         //将后n-k个元素依次与对顶元素比较
                Map.Entry<String,Integer> top=minHeap.peek();
                if(top.getValue().compareTo(entry.getValue())==0) {//频率相等
                    if(top.getKey().compareTo(entry.getKey())>0) {//字典序更小的入堆
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }else {//频率不相等,频率更大的入堆
                    if(entry.getValue().compareTo(top.getValue())>0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        List<String> list=new ArrayList<>();
        for(int i=0;i<k;i++) {
            list.add(minHeap.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }

}
